Solving 10385 - Duathlon (Ternary search)
[andmenj-acm.git] / 321 - The New Villa / 321.cpp
blob16aba816ca15f77f94547896266d6b08d19dbefd
1 /*
2 Accepted
3 */
4 #include <iostream>
5 #include <cassert>
6 #include <queue>
7 #include <vector>
8 #include <algorithm>
10 using namespace std;
12 struct state{
13 int i, lights, w;
14 state() {}
15 state(int I, int L, int W) : i(I), lights(L), w(W) {}
18 const int MAXR = 10;
20 int toggleBit(int x, int b){
21 if (x & (1 << b))
22 return x & ~(1 << b);
23 else
24 return x | (1 << b);
27 int differentBit(int x, int y){
28 return __builtin_ctz(x ^ y);
31 int main(){
32 int r, d, s, C = 1;
33 while (scanf("%d%d%d", &r, &d, &s) == 3 && (r+d+s)){
34 vector<int> doors[r], switches[r];
35 printf("Villa #%d\n", C++);
37 for (int i=0; i<d; ++i){
38 int u, v;
39 scanf("%d%d", &u, &v);
40 --u, --v;
41 doors[u].push_back(v);
42 doors[v].push_back(u);
45 for (int i=0; i<s; ++i){
46 int u, v;
47 scanf("%d%d", &u, &v);
48 --u, --v;
49 switches[u].push_back(v);
52 bool visited[(1<<MAXR)+1][MAXR] = {false};
53 state p[(1<<MAXR)+1][MAXR];
54 for (int i=0; i<=(1<<MAXR); ++i){
55 for (int j=0; j<MAXR; ++j){
56 p[i][j] = state(-1, -1, -1);
60 queue<state> q;
61 int length = -1;
62 q.push(state(0, 1<<0, 0));
63 while (q.size()){
64 state u = q.front();
65 //printf("popped state: i = %d, lights = %X, w = %d\n", u.i, u.lights, u.w);
66 q.pop();
67 if (u.i == r - 1 && u.lights == (1 << (r-1))){
68 //Solution found
69 //printf("Solution found. i = %d, lights = %X, w = %d\n", u.i, u.lights, u.w);
70 length = u.w;
71 break;
74 if (visited[u.lights][u.i]) continue;
75 visited[u.lights][u.i] = true;
77 vector<int> &s = switches[u.i];
78 for (int j=0; j<s.size(); ++j){
79 int nlights = toggleBit(u.lights, s[j]);
80 if (!visited[nlights][u.i] && (nlights & (1 << u.i))){
81 q.push(state(u.i, nlights, u.w + 1));
82 if (p[nlights][u.i].i == -1) p[nlights][u.i] = u;
83 //printf(" pushed state: i = %d, lights = %X, w = %d\n", u.i, nlights, u.w + 1);
87 vector<int> &d = doors[u.i];
88 for (int j=0; j<d.size(); ++j){ //Moverme sin apagar luces
89 if (!visited[u.lights][d[j]] && (u.lights & (1 << d[j]))){
90 q.push(state(d[j], u.lights, u.w + 1));
91 if (p[u.lights][d[j]].i == -1) p[u.lights][d[j]] = u;
92 //printf(" pushed state: i = %d, lights = %X, w = %d\n", d[j], u.lights, u.w + 1);
96 if (length == -1){
97 printf("The problem cannot be solved.\n");
98 }else{
99 printf("The problem can be solved in %d steps:\n", length);
100 vector<state> w;
101 state u = state(r-1, 1<<(r-1), -1);
102 while (p[u.lights][u.i].i != -1){
103 w.insert(w.begin(), u);
104 u = p[u.lights][u.i];
106 w.insert(w.begin(), u);
108 for (int i=0; i<w.size(); ++i){
109 printf(" state: i = %d, lights = %X, w = %d\n", w[i].i, w[i].lights, w[i].w);
111 fprintf(stderr, "w.size() = %d, length = %d\n", w.size(), length);
112 assert(w.size() == length+1);
113 for (int i=1; i<w.size(); ++i){
114 if (w[i].i != w[i-1].i){
115 printf("- Move to room %d.\n", w[i].i + 1);
116 }else{
117 printf("- Switch %s light in room %d.\n", (w[i-1].lights < w[i].lights ? "on" : "off"), differentBit(w[i-1].lights, w[i].lights) + 1);
121 printf("\n");
123 return 0;